<?php
/**
 * @title 2182. 构造限制重复的字符串
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param String $s
     * @param Integer $repeatLimit
     * @return String
     */
    function repeatLimitedString($s, $repeatLimit) {
        /**
         * @since 2024-05-20 统计字符出现次数
         */
        $charCntArray = [];
        for($i=0; $i<strlen($s); $i++){
            $c = $s[$i];
            if(isset($charCntArray[$c])){
                $charCntArray[$c][1]++;
            } else {
                $charCntArray[$c] = [$c, 1];
            }
        }
        rsort($charCntArray);

        /**
         * @since 2024-05-20 用 s 中的字符构造一个新字符串 repeatLimitedString
         */
        $newString = "";
        $left = 0;
        $right = 1;
        while(true){
            if($right <= $left) {
                $right = $left + 1;
                continue;
            } else {}
            if($right >= count($charCntArray) OR $left >= count($charCntArray)) break;

            list($c1, $n1) = $charCntArray[$left];
            list($c2, $n2) = $charCntArray[$right];
            if($n1 == 0) {
                $left++;
                continue;
            } else {}
            if($n2 == 0) {
                $right++;
                continue;
            }

            /**
             * @since 2024-05-20 c1字符可以分成r组，多m个
             */
            $r = intval($n1 / $repeatLimit);
            $m = $n1 % $repeatLimit;

            // echo "c1: $c1, n1: $n1, c2: $c2, n2: $n2, r: $r, m: $m\n";
            if($m > 0){
                /**
                 * @since 2024-05-20 c1需要r个c2来限制重复
                 */
                if($n2 >= $r){
                    $newString .= str_repeat(str_repeat($c1, $repeatLimit) . $c2, $r) . str_repeat($c1, $m);
                    $charCntArray[$left][1] = 0;
                    $charCntArray[$right][1] -= $r;
                } else {
                    $newString .= str_repeat(str_repeat($c1, $repeatLimit) . $c2, $n2);
                    $charCntArray[$left][1] -= $n2*$repeatLimit;
                    $charCntArray[$right][1] = 0;
                }
            } else {
                /**
                 * @since 2024-05-20 c1需要r-1个c2来限制重复
                 */
                if($n2 >= $r-1){
                    if($r-1 <= 0){
                        $newString .= str_repeat($c1, $repeatLimit);
                    } else {
                        $newString .= str_repeat(str_repeat($c1, $repeatLimit) . $c2, $r-1) . str_repeat($c1, $repeatLimit);
                        $charCntArray[$right][1] -= $r-1;
                    }
                    $charCntArray[$left][1] = 0;
                } else {
                    $newString .= str_repeat(str_repeat($c1, $repeatLimit) . $c2, $n2);
                    $charCntArray[$left][1] -= $n2*$repeatLimit;
                    $charCntArray[$right][1] = 0;
                }
            }
            // echo "newString: {$newString}\n";
        }

        /**
         * @since 2024-05-20 收官处理left
         */
        if(isset($charCntArray[$left]) AND $charCntArray[$left][1] > 0) $newString .= str_repeat($charCntArray[$left][0], min($repeatLimit, $charCntArray[$left][1]));

        /**
         * @return
         */
        return $newString;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202405/2024.05.20_3.php
 */
$datas = [
    ["cczazcc", 3],
    ["aababab", 2],
    ["aaaaaab", 2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    /**
     * @since 2024-01-15 超时和错误案例参数
     */
    // $data = $xhprof->FormatArgs("/tmp/leetcode/xxx-xxx.txt");

    // $data[0] = $xhprof->listNode($data[0]);
    // $data[0] = $xhprof->tree($data[0]);
    echo $xhprof->DumpArgs($data);
    echo "\n<hr>\n";

    $obj = new Solution();
    $result = $obj->repeatLimitedString(...$data);
    echo $xhprof->DumpArgs([$result]);
    var_dump($result);

    echo "\n<hr>". str_repeat("<br>", 2) . str_repeat(PHP_EOL, 5);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
